問題一覧 > 通常問題

No.649 ここでちょっとQK！

レベル : / 実行時間制限 : 1ケース 3.000秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : / 解いたユーザー数 271
作問者 : kakira9618kakira9618 / テスター : matsu7874matsu7874
14 ProblemId : 2120 / 出題時の順位表 / 自分の提出
問題文最終更新日: 2018-10-13 04:32:01

問題文

整数$Q$、$K$が与えられます。
次のクエリ（$Q$個）を処理してください。

  • タイプ1: 配列$S$に数$v$を追加する
  • タイプ2: 配列$S$の要素数が$K$以上の場合、$S$の要素のうち$K$番目に小さい要素を1つ出力し、$S$から削除する。$S$の要素数が$K$未満の場合は、-1を出力する。

（※全てのタイプ2のクエリについて、$K$は共通です）

入力

$Q$ $K$
$query_1$
$query_2$
…
$query_Q$

入力は全て整数で与えられる。

$Q (1\leq Q\leq200000)$はクエリの数を表す
$K (1\leq K\leq200000)$はタイプ2のクエリにおいて、何番目に小さい数を答えれば良いかを表す。

続く$Q$行にはクエリの情報が示される。
$query_i$ は$i$番目のクエリを表す。各クエリは次のフォーマットで与えられる。

タイプ1のクエリの場合: 
$1\ v_i$
タイプ2のクエリの場合: 
$2$

ここで、$v_i (0\leq v_i\leq10^{18})$は$i$番目のクエリ（タイプ1）において、配列に追加する数を表す。
タイプ2のクエリは1個以上存在する。

入力・出力行数が多いので、IOには気をつけてください！ 特にLL系の言語の場合は、制約がタイトなため注意してください！

出力

タイプ2のクエリによる結果を改行区切りで出力せよ。最後に改行すること。

サンプル

サンプル1
入力
15 3
1 3
1 4
1 5
2
2
1 10
1 10
1 1
2
1 3
2
1 1000
2
1 0
2
出力
5
-1
4
3
10
3

配列$S$は次のように変化します。

  • 1番目～3番目のクエリ: $S = \{3, 4, 5\}$
  • 4番目のクエリ: 5を出力、$S = \{3, 4\}$
  • 5番目のクエリ: -1を出力、$S = \{3, 4\}$
  • 6番目～8番目のクエリ: $S = \{1, 3, 4, 10, 10\}$
  • 9番目のクエリ: 4を出力、$S = \{1, 3, 10, 10\}$
  • 10番目のクエリ: $S = \{1, 3, 3, 10, 10\}$
  • 11番目のクエリ: 3を出力、$S = \{1, 3, 10, 10\}$
  • 12番目のクエリ: $S = \{1, 3, 10, 10, 1000\}$
  • 13番目のクエリ: 10を出力、$S = \{1, 3, 10, 1000\}$
  • 14番目のクエリ: $S = \{0, 1, 3, 10, 1000\}$
  • 15番目のクエリ: 3を出力、$S = \{0, 1, 10, 1000\}$
サンプル2
入力
4 1
1 10
1 10
2
2
出力
10
10

クエリによって、配列$S$の要素は重複することがあります。
重複している場合でも、タイプ2のクエリで削除される要素が１つであることに気をつけてください。

サンプル3
入力
4 2
1 9
1 10000000000000000
1 90000000000000000
2
出力
10000000000000000

大きい数が入力される場合があります。9と京と9京なので2番目に小さい京を出力します。

サンプル4
入力
1 1
2
出力
-1

提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。